/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._16_19;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

/**
 * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 *
 * 示例：
 *
 * 输入：
 * [
 *   [0,2,1,0],
 *   [0,1,0,1],
 *   [1,1,0,1],
 *   [0,1,0,1]
 * ]
 * 输出： [1,2,4]
 * 提示：
 *
 * 0 < len(land) <= 1000
 * 0 < len(land[i]) <= 1000
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._16_19
 * @ClassName: PondSizes
 * @Author: linyaonan
 * @Date: 2020/3/30 16:26
 */
public class PondSizes {

    public int[] pondSizes(int[][] land) {
        int[] xK = {0,0,-1,1,1,-1,1,-1};
        int[] yK = {-1,1,0,0,1,1,-1,-1};
        int xLength = land.length - 1;
        int yLength = land[0].length - 1;
        // 保存海域坐标
        ArrayList<int[]> ocList = new ArrayList<>();
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[i].length; j++) {
                if (land[i][j] == 0) {
                    ocList.add(new int[]{i, j});
                }
            }
        }
        ArrayList<Integer> addList = new ArrayList<>();
        for (int[] oc : ocList) {
            // 无效海域直接过滤
            if (land[oc[0]][oc[1]] != 0) {
                continue;
            }
            LinkedList<int[]> linkedList = new LinkedList<>();
            int count = 1;
            // 海域填平
            land[oc[0]][oc[1]] = 1;
            linkedList.add(oc);
            while (!linkedList.isEmpty()) {
                int[] poll = linkedList.poll();
                int x = poll[0];
                int y = poll[1];
                // 八个方向
                for (int i = 0; i < 8; i++) {
                    int moveX = x + xK[i];
                    int moveY = y + yK[i];
                    // 有效海域
                    if (moveX >= 0 && moveX <= xLength && moveY >= 0 && moveY <= yLength && land[moveX][moveY] == 0) {
                        count++;
                        // 增加下一个海域地址
                        linkedList.add(new int[]{moveX, moveY});
                        // 下一个海域填平
                        land[moveX][moveY] = 1;
                    }
                }
            }
            // 有效海域
            addList.add(count);
        }
        // 排序
        Collections.sort(addList);
        int[] ints = new int[addList.size()];
        for (int i = 0; i < addList.size(); i++) {
            ints[i] = addList.get(i);
        }
        return ints;
    }

}
